package Top_Interview_Questions_Review._009Linked_List;


import Top_Interview_Questions_Review.ListNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/10 16:55
 * <p>
 * 功能描述:
 */
public class _0206 {

    public static void main(String[] args) {
        _0206 test = new _0206();

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode reverseList = test.reverseList1(node1);
        System.out.println(reverseList);

    }
    /**
     * 迭代
     */
    public ListNode reverseList1(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }




    /**
     * 递归
     * https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
     */

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }


}
